package 贪心andDp;

import java.util.Arrays;

public class _08部分背包问题 {
    /**
     * 有n个物体，第i个物体的重量为wi，价值为vi。在总重量不超过C的情况下让总价值尽量高。
     * 每一个物体都可以只取走一部分，价值和重量按比例计算。
     * 求最大总价值
     * 注意：每个物体可以只拿一部分，因此一定可以让总重量恰好为C。
     */
    public static void main(String[] args) {
        int[] w = {1, 2, 3, 4, 5};
        int[] v = {3, 4, 3, 1, 4};
        int n = w.length;
        obj[] objs = new obj[n];
        for (int i = 0; i < n; i++) {
            objs[i] = new obj(w[i], v[i]);
        }
        Arrays.sort(objs);
        double C = 10;
        double c = C;
        double maxValue = 0;
        for (int i = n-1; i >= 0; i--) {
            if (maxValue <= c) {
                maxValue += objs[i].v;
                c -= objs[i].w;
            }else {
                maxValue += objs[i].v * (c/objs[i].w);
                break;
            }
        }
        System.out.println(maxValue);
    }

    public static class obj implements Comparable<obj> {
        int w;
        int v;

        public obj(int w, int v) {
            this.w = w;
            this.v = v;
        }

        public double getPrice() {
            return v / (double) w;
        }

        @Override
        public int compareTo(obj o) {
            if (this.getPrice() == o.getPrice()) return 0;
            else if (this.getPrice() < o.getPrice()) return -1;
            else return 1;
        }
    }
}
